#include <string>
#include <vector>
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

void dfs(TreeNode *root, vector<string> &res, string &path) {
  string val_str = to_string(root->val);
  int val_len = val_str.size();
  path += val_str;
  if (!root->left && !root->right) {
    res.push_back(path);
    path.erase(path.size() - val_len, val_len);
    return;
  }
  path += "->";
  if (root->left) {
    dfs(root->left, res, path);
  }
  if (root->right) {
    dfs(root->right, res, path);
  }
  // 删除 "->"
  path.erase(path.size() - 2, 2);
  // 删除当前加入的值
  path.erase(path.size() - val_len, val_len);
}
vector<string> binaryTreePaths(TreeNode *root) {
  vector<string> res;
  string path;
  dfs(root, res, path);
  return res;
}